package com.sise.Backtracking;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;


/**
 *      131. 分割回文串
 *
 *      给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
 *      回文串 是正着读和反着读都一样的字符串。
 *
 *      示例 1：
 *      输入：s = "aab"
 *      输出：[["a","a","b"],["aa","b"]]
 *
 *      难题：
 *          切割问题可以抽象为组合问题
 *          如何模拟那些切割线：以递归时候传递的 begin 作为当前的启动， i++ 作为字符串的终止节点
 *          切割问题中递归如何终止：当 begin == len，那么说明当前是一个完整的回文串
 *          在递归循环中如何截取子串：new String(charArray, begin, i + 1 - begin)
 *          如何判断回文：
 */
public class _131_partition {

    public List<List<String>> partition(String s) {
        int len = s.length();
        List<List<String>> res = new ArrayList<>();
        if (len == 0) {
            return res;
        }
        Deque<String> path = new ArrayDeque<>();
        char[] charArray = s.toCharArray();
        dfs(charArray, 0, len, res, path);
        return res;
    }

    /**
     * @param charArray 对于字符串的解析获取，统一使用 字符数组 会比较好
     * @param begin     当前递归的开始索引下标
     * @param len       字符串的长度
     * @param res       结果集
     * @param path      临时路径变量
     */
    private void dfs(char[] charArray, int begin, int len, List<List<String>> res, Deque<String> path) {
        // 结束条件：当前所有数字都遍历结束，对于不同结果的控制，是在分叉树枝中进行的。例如：[[a, d, b, b, c], [a, d, bb, c]]
        if (begin == len) {
            res.add(new ArrayList<>(path));
            return;
        }

        // 这里 i = begin，控制元素不重复
        for (int i = begin; i < len; i++) {
            // 随着 i++，这里的 [begin ~ i] 的长度会增加，所以此时判断回文串也需要增加。这里判断的是 [begin，i] 的字符串是否为回文串，如果不是的话就跳到下一个。
            // 例如一开始是 [a]，经过 [b,b] 是回文串后，那就是 [a,b,b]
            if (!checkPalindrome(charArray, begin, i)) {
                continue;
            }
            path.addLast(new String(charArray, begin, i + 1 - begin));
            // dfs 递归使用的是 i + 1，而不是 begin + 1。如果每次都是 begin + 1，那么 for 循环便没有意义
            // 因为这里的 for 循环会不断的增加，i 的位置指的是 已添加过路径的索引下标。例如 [a, d, bb, c] 这里的 bb 是一次性跳过两个元素的
            dfs(charArray, i + 1, len, res, path);
            path.removeLast();
        }
    }

    private boolean checkPalindrome(char[] charArray, int left, int right) {
        while (left < right) {
            if (charArray[left] == charArray[right]) {
                left++;
                right--;
            } else {
                return false;
            }
        }
        return true;
    }
}